# encoding: utf-8
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: insertion_sort.py 
@time: 2019/7/1 10:09
"""

'''
插入排序如同打扑克一样，每次将后面的牌插到前面已经排好序的牌中。插入排序有一种优化算法，叫做拆半插入。因为前面是局部排好的序列，因此可以用折半查找的方法将牌插入到正确的位置，而不是从后往前一一比对。折半查找只是减少了比较次数，但是元素的移动次数不变，所以时间复杂度仍为 O(n^2) ！
'''
def insertionSort(nums):
    for i in range(len(nums) - 1):
        # 遍历len(nums) - 1次
        curNum, preIndex = nums[i + 1], i
        # curNum保存当前待播入的数
        while preIndex >= 0 and curNum < nums[preIndex]:
            # 将比curNum大的元素向后移动
            nums[preIndex + 1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex + 1] = curNum
        # 待插入的数的正确位置
    return nums

# Example use
if __name__ == "__main__":
    nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
    print(insertionSort(nums))